package com.practice.zuocy.trainingcamp001.class02;

/**
 * 【题目】：
 * 字符串只由'0'和'1'两种字符构成，
 * 当字符串长度为1时， 所有可能的字符串为"0"、 "1";
 * 当字符串长度为2时， 所有可能的字符串为"00"、 "01"、 "10"、 "11";
 * 当字符串长度为3时， 所有可能的字符串为"000"、 "001"、 "010"、 "011"、 "100"、
 * "101"、 "110"、 "111"
 * 如果某一个字符串中， 只要是出现'0'的位置， 左边就靠着'1'， 这样的字符串叫作达
 * 标字符串。
 * 给定一个正数N， 返回所有长度为N的字符串中， 达标字符串的数量。
 * 比如， N=3， 返回3， 因为只有"101"、 "110"、 "111"达标。
 */
public class Code02_ZeroLeftOneStringNumber {

	/*
	 *
	 * 定义一个递归函数 int f(i) : 有i的长度，每个位置可以填“0”或者填“1”，这“i”个长度的最左侧一定有一个'1'字符，最终整体有多少达标的串
	 *
	 * 尝试模型：从左到右尝试模型
	 *
	 * N = 10 时，主函数调用 f(9)
	 *
	 * f(i) = f(i-2) + f(i-1) =====> F(N) = F(N-1) + F(N-2), 斐波那契数列 ----> 快速幂解法 O(logN)
	 *
	 */

	/*
	 * F(1) = 1
	 * F(2) = 2
	 * F(n) = F(n-1)+F(n-2)
	 */


	public static int getNum1(int n) {
		if (n < 1) {
			return 0;
		}
		return process(1, n);
	}

	public static int process(int i, int n) {
		if (i == n - 1) {
			return 2;
		}
		if (i == n) {
			return 1;
		}
		return process(i + 1, n) + process(i + 2, n);
	}

	public static int getNum2(int n) {
		if (n < 1) {
			return 0;
		}
		if (n == 1) {
			return 1;
		}
		int pre = 1;
		int cur = 1;
		int tmp = 0;
		for (int i = 2; i < n + 1; i++) {
			tmp = cur;
			cur += pre;
			pre = tmp;
		}
		return cur;
	}

	public static int getNum3(int n) {
		if (n < 1) {
			return 0;
		}
		if (n == 1 || n == 2) {
			return n;
		}
		int[][] base = { { 1, 1 }, { 1, 0 } };
		int[][] res = matrixPower(base, n - 2);
		return 2 * res[0][0] + res[1][0];
	}
	
	
	
	
	
	
	public static int fi(int n) {
		if (n < 1) {
			return 0;
		}
		if (n == 1 || n == 2) {
			return 1;
		}
		int[][] base = { { 1, 1 }, 
				         { 1, 0 } };
		int[][] res = matrixPower(base, n - 2);
		return res[0][0] + res[1][0];
	}

	
	
	
	public static int[][] matrixPower(int[][] m, int p) {
		int[][] res = new int[m.length][m[0].length];
		for (int i = 0; i < res.length; i++) {
			res[i][i] = 1;
		}
		int[][] tmp = m;
		for (; p != 0; p >>= 1) {
			if ((p & 1) != 0) {
				res = muliMatrix(res, tmp);
			}
			tmp = muliMatrix(tmp, tmp);
		}
		return res;
	}

	public static int[][] muliMatrix(int[][] m1, int[][] m2) {
		int[][] res = new int[m1.length][m2[0].length];
		for (int i = 0; i < m1.length; i++) {
			for (int j = 0; j < m2[0].length; j++) {
				for (int k = 0; k < m2.length; k++) {
					res[i][j] += m1[i][k] * m2[k][j];
				}
			}
		}
		return res;
	}

	public static void main(String[] args) {
		for (int i = 0; i != 20; i++) {
			System.out.println(getNum1(i));
			System.out.println(getNum2(i));
			System.out.println(getNum3(i));
			System.out.println("===================");
		}

	}
}
